// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package escape

import (
	"cmd/compile/internal/base"
	"cmd/compile/internal/ir"
	"cmd/compile/internal/logopt"
	"cmd/internal/src"
	"fmt"
	"strings"
)

// walkAll计算所有
// 位置对之间的最小解引用。
func (b *batch) walkAll() {
	// 我们使用工作队列来跟踪我们需要访问的位置，并反复步行，直到到达一个固定点。
	// 
	// 我们从每个位置（包括堆）走一次路，然后在每个位置从
	// transient->转换时重新排队！转瞬即逝！逃逸->逃逸，每个
	// 最多只能发生一次。所以我们去散步。

	// 后进先出队列，有足够的空间容纳e.allloc和e.heapLoc。
	todo := make([]*location, 0, len(b.allLocs)+1)
	enqueue := func(loc *location) {
		if !loc.queued {
			todo = append(todo, loc)
			loc.queued = true
		}
	}

	for _, loc := range b.allLocs {
		enqueue(loc)
	}
	enqueue(&b.heapLoc)

	var walkgen uint32
	for len(todo) > 0 {
		root := todo[len(todo)-1]
		todo = todo[:len(todo)-1]
		root.queued = false

		walkgen++
		b.walkOne(root, walkgen, enqueue)
	}
}

// walkOne计算从根目录到
// 所有其他位置的最小解引用次数。
func (b *batch) walkOne(root *location, walkgen uint32, enqueue func(*location)) {
	// 数据流图有负边（来自寻址
	// 操作），因此我们使用Bellman Ford算法。然而，我们不必担心无限的负循环，因为我们将中间解引用计数限制为0。

	root.walkgen = walkgen
	root.derefs = 0
	root.dst = nil

	todo := []*location{root} // 后进先出队列
	for len(todo) > 0 {
		l := todo[len(todo)-1]
		todo = todo[:len(todo)-1]

		derefs := l.derefs

		// 如果l.derefs<0，则l的地址流向根。
		addressOf := derefs < 0
		if addressOf {
			// 对于像“root=&l；l=x”这样的流路径，
			// l的地址流向root，但x的地址流向root，而
			// 不是。我们通过将
			// derefs的下限设为0来认识到这一点。
			derefs = 0

			// 如果l的地址流到一个非暂时的
			// 位置，那么l不能被暂时分配。
			if !root.transient && l.transient {
				l.transient = false
				enqueue(l)
			}
		}

		if b.outlives(root, l) {
			// l的值流向root。如果l是函数
			// 参数，而root是堆或
			// 对应的结果参数，则记录
			// 该值流，以便稍后标记函数
			// 。
			if l.isName(ir.PPARAM) {
				if (logopt.Enabled() || base.Flag.LowerM >= 2) && !l.escapes {
					if base.Flag.LowerM >= 2 {
						fmt.Printf("%s: parameter %v leaks to %s with derefs=%d:\n", base.FmtPos(l.n.Pos()), l.n, b.explainLoc(root), derefs)
					}
					explanation := b.explainPath(root, l)
					if logopt.Enabled() {
						var e_curfn *ir.Func // TODO（mdempsky）：修复。
						logopt.LogOpt(l.n.Pos(), "leak", "escape", ir.FuncName(e_curfn),
							fmt.Sprintf("parameter %v leaks to %s with derefs=%d", l.n, b.explainLoc(root), derefs), explanation)
					}
				}
				l.leakTo(root, derefs)
			}

			// 如果l的地址流到
			// 超过它的某个地方，那么需要为l分配堆
			// 地址。
			if addressOf && !l.escapes {
				if logopt.Enabled() || base.Flag.LowerM >= 2 {
					if base.Flag.LowerM >= 2 {
						fmt.Printf("%s: %v escapes to heap:\n", base.FmtPos(l.n.Pos()), l.n)
					}
					explanation := b.explainPath(root, l)
					if logopt.Enabled() {
						var e_curfn *ir.Func // TODO（mdempsky）：修复。
						logopt.LogOpt(l.n.Pos(), "escape", "escape", ir.FuncName(e_curfn), fmt.Sprintf("%v escapes to heap", l.n), explanation)
					}
				}
				l.escapes = true
				enqueue(l)
				continue
			}
		}

		for i, edge := range l.edges {
			if edge.src.escapes {
				continue
			}
			d := derefs + edge.derefs
			if edge.src.walkgen != walkgen || edge.src.derefs > d {
				edge.src.walkgen = walkgen
				edge.src.derefs = d
				edge.src.dst = l
				edge.src.dstEdgeIdx = i
				todo = append(todo, edge.src)
			}
		}
	}
}

// explainPath打印src如何流向walk root的解释。
func (b *batch) explainPath(root, src *location) []*logopt.LoggedOpt {
	visited := make(map[*location]bool)
	pos := base.FmtPos(src.n.Pos())
	var explanation []*logopt.LoggedOpt
	for {
		// 防止无限循环。
		if visited[src] {
			if base.Flag.LowerM >= 2 {
				fmt.Printf("%s:   warning: truncated explanation due to assignment cycle; see golang.org/issue/35518\n", pos)
			}
			break
		}
		visited[src] = true
		dst := src.dst
		edge := &dst.edges[src.dstEdgeIdx]
		if edge.src != src {
			base.Fatalf("path inconsistency: %v != %v", edge.src, src)
		}

		explanation = b.explainFlow(pos, dst, src, edge.derefs, edge.notes, explanation)

		if dst == root {
			break
		}
		src = dst
	}

	return explanation
}

func (b *batch) explainFlow(pos string, dst, srcloc *location, derefs int, notes *note, explanation []*logopt.LoggedOpt) []*logopt.LoggedOpt {
	ops := "&"
	if derefs >= 0 {
		ops = strings.Repeat("*", derefs)
	}
	print := base.Flag.LowerM >= 2

	flow := fmt.Sprintf("   flow: %s = %s%v:", b.explainLoc(dst), ops, b.explainLoc(srcloc))
	if print {
		fmt.Printf("%s:%s\n", pos, flow)
	}
	if logopt.Enabled() {
		var epos src.XPos
		if notes != nil {
			epos = notes.where.Pos()
		} else if srcloc != nil && srcloc.n != nil {
			epos = srcloc.n.Pos()
		}
		var e_curfn *ir.Func // TODO（mdempsky）：修复。
		explanation = append(explanation, logopt.NewLoggedOpt(epos, "escflow", "escape", ir.FuncName(e_curfn), flow))
	}

	for note := notes; note != nil; note = note.next {
		if print {
			fmt.Printf("%s:     from %v (%v) at %s\n", pos, note.where, note.why, base.FmtPos(note.where.Pos()))
		}
		if logopt.Enabled() {
			var e_curfn *ir.Func // TODO（mdempsky）：修复。
			explanation = append(explanation, logopt.NewLoggedOpt(note.where.Pos(), "escflow", "escape", ir.FuncName(e_curfn),
				fmt.Sprintf("     from %v (%v)", note.where, note.why)))
		}
	}
	return explanation
}

func (b *batch) explainLoc(l *location) string {
	if l == &b.heapLoc {
		return "{heap}"
	}
	if l.n == nil {
		// TODO（mdempsky）：完全省略。
		return "{temp}"
	}
	if l.n.Op() == ir.ONAME {
		return fmt.Sprintf("%v", l.n)
	}
	return fmt.Sprintf("{storage for %v}", l.n)
}

// outlives报告存储在l中的值是否可以在
// 如果分配堆栈，则其他值的生存期将延长。
func (b *batch) outlives(l, other *location) bool {
	// 堆比一切都长寿。
	if l.escapes {
		return true
	}

	// 我们不知道调用方如何处理返回的值，所以
	// 悲观地说，我们需要假设它们流到堆中，并且
	// 也比一切都长。
	if l.isName(ir.PPARAMOUT) {
		// 异常：直接调用的闭包可以返回在它们之外分配的
		// 位置，而无需强制将它们放入堆中。例如：
		// 
		// var u int 
		// *（func（）*int{return&u}（））=42 
		if containsClosure(other.curfn, l.curfn) && l.curfn.ClosureCalled() {
			return false
		}

		return true
	}

	// 如果l和other在同一个函数中，那么如果在other的循环
	// 比other更有效。例如：
	// 范围之外声明，那么l 
	// 
	// var l*int 
	// For{
	// l=new（int）
	// }
	if l.curfn == other.curfn && l.loopDepth < other.loopDepth {
		return true
	}

	// 如果在
	// 声明的子闭包中声明了其他，那么l将超过它。例如：
	// 
	// var l*int 
	// func（）{
	// l=new（int）
	// }
	if containsClosure(l.curfn, other.curfn) {
		return true
	}

	return false
}

// containsClosure报告c是否包含在f中。
func containsClosure(f, c *ir.Func) bool {
	// Common case。
	if f == c {
		return false
	}

	// 函数Foo中的闭包的名称类似于“Foo.funcN…”
	// TODO（mdempsky）：更好地认识到这一点。
	fn := f.Sym().Name
	cn := c.Sym().Name
	return len(cn) > len(fn) && cn[:len(fn)] == fn && cn[len(fn)] == '.'
}
